///////////////////////////////////      弗洛伊德算法
void floyd(int k,vector<vector<int>>& graph,int n){ //弗洛伊德最短路径算法的有点在于可以后续动态扩充图从而找到更短路径
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(i!=j&&graph[i][j]>graph[i][k]+graph[k][j]){
				graph[i][j]=graph[i][k]+graph[k][j];
			}
		}
	}
	
	return;
}

///////////////////////////////////      堆优化迪杰斯特拉模板
class edge {
public:
    int end, w, g; //end为该边到达的终点 w为该边的花费 g为该边可获得心情指数
    edge(int end=0, int w=0, int g=0) : end(end), w(w), g(g) {}
    
    
    bool operator<(const edge& other) const {
        if(w == other.w) return g < other.g; 
        return w > other.w; // 小顶堆
    }
};

void dij(vector<vector<edge>> &graph, int n, int st, int b) {
    vector<int> dis(n+1, INF), mood(n+1, 0);
    dis[st] = 0;
    
    priority_queue<edge> pq; // 优先队列排序规则：旅费小优先，旅费相同则心情值大优先
    pq.push(edge(st, 0, 0)); // 初始状态：起点旅费0，心情0

    while(!pq.empty()) {
        auto [e, w, g] = pq.top(); // 当前节点信息
        pq.pop();
        
        if(w > dis[e]) continue; // 如果我从源点到达点e的花费w比已记录dis[e]还要大 那么根本没必要更新

        for(auto& [e0, w0, g0] : graph[e]) { // 遍历点e的邻接节点
            int new_cost = w + w0;
            int new_mood = g + g0;
            
            if(new_cost > b) continue; // 超出预算直接跳过

            // 发现更优路径
            if(new_cost < dis[e0]) { //如果经过e到达邻接点e0的花费 比已记录到达点e0的花费dis[e0]还要小 更新dis[e0]和mood 并将该边压入优先队列
                dis[e0] = new_cost;
                mood[e0] = new_mood;
                pq.push(edge(e0, new_cost, new_mood));
            } 
           
            else if(new_cost == dis[e0] && new_mood > mood[e0]) {  // 旅费相同则选择心情更好的
                mood[e0] = new_mood;
                pq.push(edge(e0, new_cost, new_mood));
            }
        }
    }

    // 结果收集
    vector<int> ans1, ans2;
    int max_mood = -1;
    for(int i=1; i<=n; ++i) {
        if(i != st && dis[i] <= b) { //选择不是源点且可以到达的城市(即到达该城市的花费比b小)
            ans1.push_back(i);
            if(mood[i] > max_mood) {
                max_mood = mood[i];
                ans2 = {i};
            } else if(mood[i] == max_mood) {
                ans2.push_back(i);
            }
        }
    }

    // 输出处理
    if(ans1.empty()) {
        cout << "T_T" << endl;
    } else {
        sort(all(ans1)); //升序处理
        sort(all(ans2));
        for(int i=0; i<ans1.size(); ++i) 
            cout << ans1[i] << " \n"[i==ans1.size()-1];
        for(int i=0; i<ans2.size(); ++i)
            cout << ans2[i] << " \n"[i==ans2.size()-1];
    }
}